//
//  28. 实现strStr().swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/7/11.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution28 {
    // 字符串的匹配就是kmp算法
    func strStr(_ haystack: String, _ needle: String) -> Int {
        guard needle.count > 0 else {
            return 0
        }
        let haystackArray = Array(haystack)
        let needleArray = Array(needle)
        
        // 前缀表只是为了做回退。不必要从头开始匹配。
        let next = getNext(needleArray)
        
        var i = 0 // 文本串
        var j = 0 // 模式串(模式串要不断的回退)
        while i < haystackArray.count {
            // 模式串不断回退，然后再次比较
            while j > 0 && haystackArray[i] != needleArray[j] {
                // 回退关键
                j = next[j - 1]
            }
            // 都向下走
            if haystackArray[i] == needleArray[j] {
                j += 1
            }
            // 到达了模式串的长度（说明匹配上了）
            if j == needleArray.count {
                return i - needleArray.count + 1
            }
            i += 1
        }
        return -1
    }
    
    func getNext(_ s: [Character]) -> [Int] {
        var next: [Int] = Array(repeating: 0, count: s.count)
        
        var j = 0
        var i = 1
        next[0] = j
        while i < s.count {
            // 不相等时, j要进行回退
            while j > 0 && s[j] != s[i] {
                j = next[j - 1]
            }
            // 相等一起向后走
            if s[j] == s[i] {
                j += 1
            }
            next[i] = j
            i += 1
        }
        return next
    }
    
    static func test() {
        let haystack = "aabaabaafa"
        let needle = "aabaaf"
        let solution = Solution28()
        let result = solution.strStr(haystack, needle)
        print(result)
    }
}
